package com.yupi.springbootinit.utils;

import java.util.List;

/**
 * @ClassName RecommentUtils
 * @Description 推荐算法工具类
 * @Author junjun
 * @Date 2023/5/27 23:41
 * @Version V1.0
 */
public class RecommendUtils {
    /**
     * 计算两个字符串的相似度，最小编辑距离
     * @param string1
     * @param string2
     * @return
     */
    public static int minDistance(String string1, String string2) {
        int length1 = string1.length();
        int length2 = string2.length();
        int[][] dp = new int[length1 + 1][length2 + 1];
        for (int i = 0; i <= length1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= length2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= length1; i++) {
            char c1 = string1.charAt(i - 1);
            for (int j = 1; j <= length2; j++) {
                char c2 = string2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    int replace = dp[i - 1][j - 1] + 1;
                    int insert = dp[i][j - 1] + 1;
                    int delete = dp[i - 1][j] + 1;
                    dp[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        return dp[length1][length2];

    }

    public static int minDistance(List<String> list1, List<String> list2) {
        int length1 = list1.size();
        int length2 = list2.size();
        int[][] dp = new int[length1 + 1][length2 + 1];
        for (int i = 0; i <= length1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= length2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= length1; i++) {
            String c1 = list1.get(i - 1);
            for (int j = 1; j <= length2; j++) {
                String c2 = list2.get(j - 1);
                if (c1.equals(c2)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    int replace = dp[i - 1][j - 1] + 1;
                    int insert = dp[i][j - 1] + 1;
                    int delete = dp[i - 1][j] + 1;
                    dp[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        return dp[length1][length2];
    }


}
